export const mergeSort = (arr) => {
    sort(arr, 0, arr.length - 1)
    return arr
}

const sort = (arr, l, r) => {
    if (l >= r) {
        return
    }

    const mid = Math.floor((l + r) / 2)
    sort(arr, l, mid)
    sort(arr, mid + 1, r)
    merge(arr, l, mid, r)
}

// 合并两个有序的区间 arr[l, mid] arr[mid+1, r]
const merge = (arr, l, mid, r) => {
    const arrCopy = arr.slice(l, r + 1)
    let i = l
    let j = mid + 1

    for (let k = l; k <= r; k++) {
        if (i > mid) {
            arr[k] = arrCopy[j - l]
            j++

        } else if (j > r) {
            arr[k] = arrCopy[i - l]

        } else if (arrCopy[i - l] < arrCopy[j - l]) {
            arr[k] = arrCopy[i - l]
            i++

        } else {
            arr[k] = arrCopy[j - l]
            j++

        }

    }

}

export const mergeSort2 = (arr) => {
    sort2(arr, 0, arr.length - 1)
    return arr
}

const sort2 = (arr, l, r) => { // 对有序数组的优化
    if (l >= r) {
        return
    }

    const mid = Math.floor((l + r) / 2)
    sort2(arr, l, mid)
    sort2(arr, mid + 1, r)

    if (arr[mid] > arr[mid + 1]) {
        merge(arr, l, mid, r)
    }

}

export const mergeSortBU = (arr) => {
    const arrCopy = arr.slice(0, arr.length)

    for (let size = 1; size < arr.length; size += size) {
        for (let i = 0; i + size < arr.length; i += size * 2) {
            if (arr[i + size - 1] > arr[i + size]) {
                merge2(arr, i, Math.min(i + size * 2 - 1, arr.length - 1), arrCopy)

            }
        }
    }

    return arr
}

const merge2 = (arr, l, mid, r, arrCopy) => {
    // const arrCopy = arr.slice(l, r + 1)
    let i = l
    let j = mid + 1

    for (let k = l; k <= r; k++) {
        if (i > mid) {
            arr[k] = arrCopy[j - l]
            j++

        } else if (j > r) {
            arr[k] = arrCopy[i - l]

        } else if (arrCopy[i - l] < arrCopy[j - l]) {
            arr[k] = arrCopy[i - l]
            i++

        } else {
            arr[k] = arrCopy[j - l]
            j++

        }

    }

}


export const mergeSort3 = (arr) => {

    if (arr.length < 2) {
        return arr
    }

    if (arr.length == 2) {
        return arr[0] > arr[1] ? [arr[1], arr[0]] : arr
    }

    const middle = Math.floor(arr.length / 2)
    const leftArr = arr.slice(0, middle)
    const rightArr = arr.slice(middle)

    const leftSortedArr = mergeSort3(leftArr)
    const rightSortedArr = mergeSort3(rightArr)

    const mergedArr = []
    let leftIndex = 0
    let rightIndex = 0

    while (
        leftIndex < leftSortedArr.length ||
        rightIndex < rightSortedArr.length
    ) {

        if (
            leftIndex >= leftSortedArr.length ||
            leftSortedArr[leftIndex] > rightSortedArr[rightIndex]
        ) {
            mergedArr.push(rightSortedArr[rightIndex])
            rightIndex++

        } else {
            mergedArr.push(leftSortedArr[leftIndex])
            leftIndex++

        }

    }

    return mergedArr
}